This invention relates to the routing of telecommunications traffic in anetwork comprising a plurality of nodes interconnected by paths or links. In particular, the invention relates to a method and apparatus for operating a network by defining a traffic routing plan for such a network and to a method of routing traffic via the routing plan.
As telecommunications networks become more complex and the traffic load increases there is a need to determine the routing of traffic within a network so as to provide efficient utilisation of communication channels used, and to minimise the total cost to the system operator. An approach to the problem of routing is described by A. Albanese et al. in xe2x80x9cA Routing Strategy for Interconnecting High Speed Metropolitan Area Networksxe2x80x9d, Bell Communication Research Inc. An article entitled xe2x80x9cAddressing, Bridging and Source Routingxe2x80x9d by R C Dixon et a in IEEE Network Vol 2 No 1 January 1988 describes ways for a source to determine a route through local networks using a dynamic discovery procedure whereby possible paths to a target are explored by sending control frames throughout the network.
A particular problem that frequently confronts network operators is a business customer request to provide a number of permanent virtual circuits between two network nodes. To provide these circuits the operator must choose a route across the network which takes account of cost and of available bandwidth. At present, traffic routing is determined largely on an empirical basis as a full analysis of a complex network to obtain an analytical solution is an intractable problem. It is thus very difficult for an operator to ensure that a network is used with a high degree of efficiency under all traffic conditions.
An object of the present invention is to minimise or to overcome this disadvantage.
A further object of the invention is to provide an improved method of determining routing information in a telecommunications network.
According to one aspect of the invention there is provided a method of operating a telecommunications network whereby to determine traffic routing, said network comprising a plurality of nodes interconnected by communications links and each said link incorporating one or more communications channels, wherein the method includes, providing a map or model of the network, determining in the model first and second nodes between which a communications path or route comprising a chain of links is to be established across the network, allocating to each said link a cost value representative of the operational cost of that link, creating a set or colony of exploratory agents at said first node, permitting the agents at said first node to explore the model network via the links and nodes between said first and second nodes, determining for each said agent the nodes and links visited by that agent whereby to inhibit more than one traversal of a said link by that agent, recording the results of said exploration by providing on each traversed path a marker whose value relates to the total cost of the path and the number of agents selecting that path, and determining from said results a route favoured by a significant number of said agents and setting up said route on the telecommunications network, wherein each said agent arriving via a link at a network node selects a link by which to leave that node on a probability based choice weighted with the respective cost and marker values of the respective links whereby to select preferentially a link of lower cost.
According to another aspect of the invention there is provided apparatus for operating a telecommunications network whereby to determine traffic routing within the network, said network comprising a plurality of nodes interconnected by communications links and each said link incorporating one or more communications channels, wherein the apparatus includes, means for providing a map or model of the network, means for determining in the model first and second nodes between which a communications path or route comprising a chain of links is to be established across the network, means for allocating to each said link a cost value representative of the operational cost of that link, means for creating a set or colony of exploratory agents at said first node and for permitting the agents at said first node to explore the model network via the links and nodes between said first and second nodes, means for determining for each said agent the nodes and links visited by that agent whereby to inhibit more than one traversal of a said link by that agent, means for recording the results of said exploration by providing on each traversed path a marker whose value relates to the total cost of the path and the number of agents selecting that path, and means for determining from said results a route favoured by a significant number of said agents and setting up said route on the telecommunications network, wherein each said agent arriving via a link at a network node has means for selecting a link by which to leave that node on a probability based choice weighted with the respective cost and marker values of the respective links whereby to select preferentially a link of lower cost.
The exploratory agents are individually of very limited intelligence. Initially they explore the network selecting links based on the link cost, but as the search develops paths are found which are traversed preferentially by the agents. The process may be employed by a network operator to allocate circuits in response to customer requests.
The method is of particular application to ATM networks, but it is not of course limited to networks of this type.